import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-09-28
 * Time: 15:30
 */
class Solution12 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> vis = new HashSet<>();//用来标记搜索过的数组
        Set<String> hash = new HashSet<>();//用于统计基因库里面的字符串
        char[] change = {'A','C','G','T'};
        for(String s : bank) {
            hash.add(s);
        }

        // 特殊判断
        if(startGene.equals(endGene)) {
            return 0;
        }

        if(!hash.contains(endGene)) {
            return -1;
        }
        // 准备工作
        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step = 0;

        while(!q.isEmpty()) {
            int size = q.size();
            step++;
            while(size-- != 0) {
                String t = q.poll();
                for(int i = 0; i < 8; i++) {
                    char[] tmp = t.toCharArray();
                    for(int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        String next = new String(tmp);
                        if(hash.contains(next) && !vis.contains(next)) {
                            if(next.equals(endGene)) {
                                return step;
                            }
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
